The present invention relates in general to programmed data processing systems, and in particular to programmable deterministic finite state automata machines and graphical user interface (GUI) systems.
A finite state automation, also called a xe2x80x9cfinite state machinexe2x80x9d or xe2x80x9ctransducer,xe2x80x9d consists of a set of states, a set of input events, a set of output events, and a state transition function. The set of states includes an internal state. Some states may be designed as xe2x80x9cterminal states.xe2x80x9d The state transition function takes the current state in an input event and returns the new set of output events and the next state. The finite state machine can also be viewed as a function which maps an ordered sequence of input events onto a corresponding sequence of output events.
A deterministic finite state automation is one where each next state is uniquely determined by a single input event. A deterministic finite state automation is contrasted with a backtracking automation, where at each state there may be several possible actions and the only way to choose between them is to try each one and backtrack if that transition fails.
A deterministic finite state automation can be depicted in a variety of manners well-recognized within the mathematical art. One way in which a deterministic finite state automation might be depicted is in a table format. For example:
For greater clarity, a deterministic finite state automation may be depicted graphically as in FIG. 1, which illustrates the automation of the table. The first row of the table format is depicted by a Begin state 101. The next state listed on the table is A 103. Movement is made from the Begin state 101 to the A state 103 upon a starting condition 111. Likewise, the diagram illustrates that state B 105 has exit conditions for 5119 and 6121, and state C 107 has an exit condition 4117.
Finite state automata have been reduced to programming code, as demonstrated by FIG. 2. Subroutines may be used to represent states. For example, subroutine A 210 may represent state A 103 on FIG. 1, or the first line in the table. While FIG. 2 demonstrates iterative meta-code to implement the finite state automation shown in the table above and FIG. 1, those skilled in the art will appreciate that deterministic finite state automata may be implemented in a variety of programming languages to achieve results similar to the results obtained from the pseudo-code in FIG. 2. Deterministic finite state automation are well-suited to being programmed in object-oriented languages. In fact, object-oriented languages have heretofore been considered ideal for computer implementation of the deterministic finite state automata model.
Those skilled in the art will appreciate, however, that, regardless of the language used, computer implementation of such deterministic finite state automata is often complex. The coding required to mimic a finite state automation within a computer requires special skills and training. It cannot be done by the ordinary user. Once a finite state automation is reduced to code, modifications to the finite state automation must be done by a programmer with specific training in the language in which the finite state automation is written. The instant invention addresses the complexities inherent in this system of deterministic finite state automata implementation and renders a more user-friendly system in which finite state automata may be easily implemented and modified.
The invention is a graphical-oriented editor that greatly simplifies the creation, testing, and subsequent revision of deterministic finite state automata. The editor is based upon the concept of functional units (FUs). Each FU represents a state in a deterministic finite state automation. Each FU is an object that facilitates the meaningful connection to other FUs to construct a larger logical entity which is an activity functional unit (AFU). Any AFU may be treated as a FU and nested.
By manipulating FUs and defining relationships between them graphically on the screen, the instant invention allows a user to build a complete program from FUs and AFUs. The resulting program is itself an AFU and can be combined with other AFUs and previously created AFUs to build large, complex programs.
Three control structures are necessary to implement to any program: sequence, branching, and iteration. Therefore, the instant invention provides for each of these features in order to permit construction of the most powerful and fully functional programs.
A database structure is also disclosed for facilitation of the display of the FU and the AFU in the graphical environment.
The development cycle for products built from AFUs through the instant graphical editor is considerably shorter than the development cycle for products constructed in a more traditional coding manner. Consequently, the cost of development is decreased. Short development cycles also enable development groups to more quickly respond to product management and marketing requirements.
The use of FUs and the graphic editor also considerably reduces the complexity of modifications to existing programs. Consequently, the cost of upkeep and maintenance of programs is decreased. Development groups are also able to then respond quickly to modification requirements.
The foregoing outlines broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter, which form the subject of the claims of the invention.